package algorithm.swordoff;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 机器人的运动范围
 *
 * 这题有个傻逼的地方在于可以进入的格子是数位之和小于K而不是坐标之和小于k
 * 广度优先搜索-队列
 * 深度优先搜索-递归
 */


// 机器人可以到达的格子坐标满足的**必要不充分条件**是格子坐标没有越界并且i/10 + i%10 + j/10 + j%10 <= k
// 满足这个必要不充分条件的格子可以画成下面的图,例子是16,16,6
//
//     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
//  0  T  T  T  T  T  T  T           T  T  T  T  T  T
//  1  T  T  T  T  T  T              T  T  T  T  T   
//  2  T  T  T  T  T                 T  T  T  T      
//  3  T  T  T  T                    T  T  T         
//  4  T  T  T                       T  T            
//  5  T  T                          T               
//  6  T                    .                        
//  7                   ... .                        
//  8                   ... .                        
//  9                   ... .                        
// 10  T  T  T  T  T  T              T  T  T  T  T   
// 11  T  T  T  T  T                 T  T  T  T     
// 12  T  T  T  T                    T  T  T    
// 13  T  T  T                       T  T     
// 14  T  T                          T      
// 15  T                                 
//
// 注意了,这题前提是机器人从左上角开始,像上面这个四个三角是不连通的,机器人从(0,0)只能行动到左上角这个三角,故答案是左上三角面积=28
// 因此机器人可以到达的格子坐标满足的**必要充分条件**是格子坐标没有越界并且i/10 + i%10 + j/10 + j%10 <= k  并且  与0,0这个格子是联通的


public class SQ13 {

    public int movingCount(int m, int n, int k) {
        Queue<int[]> queue = new LinkedList<>();
        List<int[]> result = new LinkedList<>();
        boolean[][] isSearched = new boolean[m][n];

        queue.add(new int[]{0,0});
        isSearched[0][0] = true;

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            result.add(poll);
            if (poll[0]+1 < m && poll[1] < n && isLessThanK(poll[0]+1, poll[1], k) && !isSearched[poll[0]+1][poll[1]]) {
                isSearched[poll[0]+1][poll[1]] = true;
                queue.add(new int[]{poll[0]+1, poll[1]});
            }

            if (poll[0] < m && poll[1]+1 < n && isLessThanK(poll[0], poll[1]+1, k) && !isSearched[poll[0]][poll[1]+1]) {
                isSearched[poll[0]][poll[1]+1] = true;
                queue.add(new int[]{poll[0], poll[1]+1});
            }
        }
        return result.size();
    }

    public boolean isLessThanK(int i, int j, int k) {
        return i/10 + i%10 + j/10 + j%10 <= k;
    }

    public int movingCount2(int m, int n, int k) {
        boolean[][] isAccessible = new boolean[m][n];
        int dfs = dfs(0, 0, m, n, k, isAccessible);
        // for (boolean[] booleans : visited) {
        //     System.out.print(Arrays.toString(booleans));
        //     System.out.print("\n");
        // }
        return dfs;
    }

    private int dfs(int i, int j, int m, int n, int k, boolean[][] isAccessible) {
        if (i < 0 || i >= m || j < 0 || j >= n || (i/10 + i%10 + j/10 + j%10) > k || isAccessible[i][j]) {
            return 0;
        }
        isAccessible[i][j] = true;
        return dfs(i + 1, j, m, n, k, isAccessible) + dfs(i, j + 1, m, n, k, isAccessible) + 1;
    }

    public static void main(String[] args) {
        SQ13 sq13 = new SQ13();
        // System.out.println(sq13.movingCount(11, 8, 16));
        System.out.println(sq13.movingCount2(16, 16, 6));
    }

}
